import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author KenLiang
 * @description:
 * @date Created in 10:40 AM 2020/11/11.
 */
public class LeetCodeTest {

    @Test
    public void Test() {
//        ListNode listNode1 = new ListNode();
//        ListNode listNode11 = new ListNode();
//        ListNode listNode111 = new ListNode();
//        listNode1.val = 2;
//        listNode11.val = 3;
//        listNode111.val = 4;
//        listNode1.next = listNode11;
//        listNode11.next = listNode111;
//
//        ListNode listNode2 = new ListNode();
//        ListNode listNode22 = new ListNode();
//        ListNode listNode222 = new ListNode();
//        listNode2.val = 2;
//        listNode22.val = 6;
//        listNode222.val = 8;
//        listNode2.next = listNode22;
//        listNode22.next = listNode222;
////        ListNode listNode = this.addTwoNumbers(listNode1, listNode2);
////        System.out.println();
////        System.out.println(Integer.MAX_VALUE);
////        System.out.println(Integer.MIN_VALUE);
////        String s = this.longestCommonPrefix(new String[]{"fllllll", "flow", "flight"});
////        System.out.println(s);
//
//        this.mergeTwoLists(listNode1, listNode2);
//        System.out.println();
//        System.out.println(this.isValid("]"));
//        int i = removeDuplicates(new int[]{1, 1, 2});
//        System.out.println();
//        int i = removeElement(new int[]{3,2,2,3},2);
//        System.out.println();
        System.out.println((int)'你');
    }


//    public int searchInsert(int[] nums, int target) {
//        for(){
//
//        }
//    }

    //根据char获取整形对应数字，结合字符串index求hashCode,比较hashCode,每次只需要把前一个去除，加入新的一个时间复杂度为O(n)
    public int strStr(String haystack, String needle) {
        if(needle.length() ==0){
            return 0;
        }
        return 0;
    }

    public int removeElement(int[] nums, int val) {
        int j =0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=val){
                nums[j++]=nums[i];
            }
        }
        return j;
    }

    public int removeDuplicates(int[] nums) {
        int z=1;
        for(int i=0,j=1;j<nums.length;j++){
            if(nums[i]!=nums[j]){
                nums[z++]=nums[j];
                i=j;
            }

        }
        return z+1;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode headNode = new ListNode();
        ListNode listNode = headNode;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                listNode.next = l1;
                l1 = l1.next;
            } else {
                listNode.next = l2;
                l2 = l2.next;
            }
            listNode = listNode.next;

        }
        listNode.next = l1== null ? l2 : l1;
        return headNode.next;
    }

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        if(l1 == null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(l1.val <=l2.val){
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists2(l1,l2.next);
            return l2;
        }
    }


    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            boolean ifTrue = true;
            char c = s.charAt(i);
            if (c == '[' || c == '{' || c == '(') {
                stack.push(c);
            } else if (!stack.isEmpty()) {
                Character pop = stack.pop();
                switch (pop) {
                    case '[':
                        ifTrue = c == ']';
                        break;
                    case '{':
                        ifTrue = c == '}';
                        break;
                    case '(':
                        ifTrue = c == ')';
                        break;
                    default:
                        ifTrue = false;
                }
            } else {
                return false;
            }
            if (!ifTrue) {
                return false;
            }

        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;

    }

    //别的方法，分而治之，最短字符串二分查找
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minLength) {
                minLength = strs[i].length();
            }

        }
        if (minLength == 0) {
            return "";
        }
        String strsResult = "";
        for (int i = 0; i < minLength; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (c != strs[j].charAt(i)) {
                    return strsResult;
                }
            }
            strsResult = strsResult + c;
        }
        return strsResult;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int nodeNum1 = 0;
        int nodeNum2 = 0;
        boolean lastAdd = false;
        int sum = 0;
        ListNode headNode = null;
        ListNode tailNode = null;
        do {

            nodeNum1 = l1 == null ? 0 : l1.val;
            nodeNum2 = l2 == null ? 0 : l2.val;
            sum = lastAdd ? (nodeNum1 + nodeNum2) + 1 : (nodeNum1 + nodeNum2);

            ListNode listNode = new ListNode();
            listNode.val = sum % 10;

            if (headNode == null) {
                headNode = listNode;
            }


            if (tailNode == null) {
                tailNode = listNode;
            } else {
                tailNode.next = listNode;
                tailNode = listNode;
            }

            if (sum > 9) {
                lastAdd = true;
            } else {
                lastAdd = false;
            }
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        } while (l1 != null || l2 != null);

        if (lastAdd) {
            ListNode listNode = new ListNode();
            listNode.val = 1;

            if (tailNode == null) {
                tailNode = listNode;
            } else {
                tailNode.next = listNode;
                tailNode = listNode;
            }
        }
        return headNode;
    }

    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        Integer num = null;
        for (int i = 0; i < nums.length; i++) {
            num = target - nums[i];
            Integer numIndex = map.get(num);
            if (numIndex != null) {
                answer[0] = i;
                answer[1] = numIndex;
                break;
            }
            map.put(nums[i], i);

        }
        return answer;
    }
}
